We study the construction of the minimum cost spanning geometric graph of agiven rooted point set $P$ where each point of $P$ is connected to the root bya path that satisfies a given property. We focus on two properties, namely themonotonicity w.r.t. a single direction ($y$-monotonicity) and the monotonicityw.r.t. a single pair of orthogonal directions ($xy$-monotonicity). We proposealgorithms that compute the rooted $y$-monotone ($xy$-monotone) minimumspanning tree of $P$ in $O(|P|\log^2 |P|)$ (resp. $O(|P|\log^3 |P|)$) time whenthe direction (resp. pair of orthogonal directions) of monotonicity is given,and in $O(|P|^2\log|P|)$ time when the optimum direction (resp. pair oforthogonal directions) has to be determined. We also give simple algorithmswhich, given a rooted connected geometric graph, decide if the root isconnected to every other vertex by paths that are all monotone w.r.t. the samedirection (pair of orthogonal directions).
展开▼
机译：我们研究了给定的根点集$ P $的最小成本跨度几何图的构造，其中$ P $的每个点都通过满足给定属性的路径连接到根。我们关注两个属性，即单调性w.r.t.单向（$ y $-单调性）和单调性一对正交方向（$ xy $-单调性）。我们提出了一些算法，用于计算$ O（| P | \ log ^ 2 | P |）$（分别是$ O（| P | \\）中的$ P $的有根$ y $-单调（$ xy $ -monotone）最小生成树。 log ^ 3 | P |）$）时间，当给出单调性的方向（正交对方向）时，而在$ O（| P | ^ 2 \ log | P |）$时，最优方向（resp。一对正交方向）。我们还给出了简单的算法，给定一个有根的连接几何图，该算法确定该根是否通过所有单调的路径连接到其他每个顶点。相同方向（一对正交方向）。
展开▼
